import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 06
 * Time: 13:36
 */
//牛客 有重复项数字的全排列
public class Solution7 {
    //法一
    ArrayList<ArrayList<Integer>> ret;
    ArrayList<Integer> path;
    boolean[] check;
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[num.length];
        Arrays.sort(num);
        dfs(num);
        return ret;
    }
    private void dfs(int[] num) {
        if(path.size() == num.length) {
            ret.add(new ArrayList<>(path));//注意add的是new ArrayList<>(path)
            return ;
        }
        for (int i = 0; i < num.length; i++) {
            if(check[i] == false && (i == 0 || num[i] != num[i - 1] || check[i - 1] == true)) {//剪枝
                path.add(num[i]);
                check[i] = true;
                dfs(num);//每递归到下一层，path就会add多一个元素
                //回溯 回溯完成之后再恢复现场(也可以恢复现场之后再回溯，但这样写法会麻烦一点)
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }




/*//法二
ArrayList<ArrayList<Integer>> ret;
    ArrayList<Integer> path;
    boolean[] check;
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[num.length];
        Arrays.sort(num);
        dfs(num);
        return ret;
    }
    private void dfs(int[] num) {
        if(path.size() == num.length) {
            ret.add(new ArrayList<>(path));//注意add的是new ArrayList<>(path)
            return ;
        }
        for (int i = 0; i < num.length; i++) {
            if(check[i] == true || (i != 0 && num[i] == num[i - 1] && check[i - 1] == false)) {//剪枝
                continue;
            }
            path.add(num[i]);
            check[i] = true;
            dfs(num);//每递归到下一层，path就会add多一个元素
            //回溯 回溯完成之后再恢复现场(也可以恢复现场之后再回溯，但这样写法会麻烦一点)
            check[i] = false;
            path.remove(path.size() - 1);
        }
    }




    //法三 结合法一和法二
    ArrayList<ArrayList<Integer>> ret;
    ArrayList<Integer> path;
    boolean[] check;
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[num.length];
        Arrays.sort(num);
        dfs(num);
        return ret;
    }
    private void dfs(int[] num) {
        if(path.size() == num.length) {
            ret.add(new ArrayList<>(path));//注意add的是new ArrayList<>(path)
            return ;
        }
        for (int i = 0; i < num.length; i++) {
            if(i != 0 && num[i] == num[i - 1] && check[i - 1] == false) {
                continue;
            }
            if(check[i] == false) {//剪枝
                path.add(num[i]);
                check[i] = true;
                dfs(num);//每递归到下一层，path就会add多一个元素
                //回溯 回溯完成之后再恢复现场(也可以恢复现场之后再回溯，但这样写法会麻烦一点)
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }*/
}
